/**
 * Created with IntelliJ IDEA.
 * Description:
 * User:何人亮
 * Date:2024-07-26
 * 13:08
 */
public class HeapSort {
    public static void  HeapSort(int[] array){//堆排序
        CreatHeap(array);
        int end=array.length-1;
        while (end>0){
            swap(array,0,end);
            siftdown(array,0,end);
            end--;
        }
    }

    public static void CreatHeap(int[] array){
        for (int parent = (array.length-1-1)/2; parent >=0; parent--) {
            siftdown(array,parent,array.length);
        }
    }
    public static void siftdown(int[] array,int parent,int len){
        int child=2*parent+1;
        while (child<len){
            if(child+1<len&&array[child+1]>array[child]){
                child++;
            }
            if(array[parent]<array[child]){
               swap(array,parent,child);
                parent=child;
                child=2*parent+1;
            }else {
                break   ;
            }
        }
    }
    public static void swap(int[] array,int i,int j){
        int tem=array[i];
        array[i]=array[j];
        array[j]=tem;
    }
}
